package primary.code04_List;

import primary.util.ListUtils;

/**
 * 将链表进行分组
 * <p>
 * 思路：
 * 方案1，将链表放到数组中，分组后再组成链表，该方法空间复杂度为O(N)
 * 方案2，分割为 < = > 三个子串，然后组合
 */
public class Code04_PartList {

    private static Node partList(Node head, int val) {
        if (head == null || head.next == null) return head;
        Node res = null;
        Node cur = head;
        Node lh = null;
        Node eh = null;
        Node gh = null;
        Node lt = null;
        Node et = null;
        Node gt = null;
        //划分
        while (cur != null) {
            if (cur.getData() < val) {
                if (lt == null) {
                    lh = lt = cur;
                } else {
                    lt.next = cur;
                    lt = lt.next;//注意
                }
            }
            if (cur.getData() == val) {
                if (et == null) {
                    eh = et = cur;
                } else {
                    et.next = cur;
                    et = et.next;
                }
            }
            if (cur.getData() > val) {
                if (gt == null) {
                    gh = gt = cur;
                } else {
                    gt.next = cur;
                    gt = gt.next;
                }
            }
            Node pre = cur;
            cur = cur.next;
            pre.next = null;
        }
        //组合
        if (lt != null) {
            lt.next = eh;
            res = lh;
            et = et != null ? et : lt;
        }
        if (et != null) {
            et.next = gh;
            res = res != null ? res : eh;
        }
        res = res != null ? res : gh;
        return res;
    }

    private static Node partList0(Node head, int val) {
        if (head == null || head.next == null) return head;

        // 占位，处理无节点的特殊情况
        Node ltemp = new Node(0);
        Node etemp = new Node(0);
        Node gtemp = new Node(0);

        Node lh = ltemp;
        Node lt = ltemp;
        Node eh = etemp;
        Node et = etemp;
        Node gh = gtemp;
        Node gt = gtemp;

        Node cur = head;
        while (cur != null) {
            if (cur.data < val) {
                lt.next = cur;
                lt = cur;
            } else if (cur.data == val) {
                et.next = cur;
                et = cur;
            } else {
                gt.next = cur;
                gt = cur;
            }
            Node next = cur.next;
            cur.next = null;
            cur = next;
        }
        lt.next = eh;
        et.next = gh;

        lh = lh.next;
        lt.next = eh.next;
        et.next = gh.next;

        return lh;
    }

    /**
     * 原链表：111-->23-->18-->41-->25-->18-->
     * 反转链表：23-->18-->18-->25-->111-->41-->
     */
    public static void main(String[] args) {
        Node node1 = new Node(111);
        Node node2 = new Node(23);
        Node node3 = new Node(18);
        Node node4 = new Node(41);
        Node node5 = new Node(25);
        Node node6 = new Node(18);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        System.out.println("原链表：" + ListUtils.printList(node1));
        System.out.println("反转链表：" + ListUtils.printList(partList0(node1, 25)));
    }
}
